package 程序员面试金典;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 最长单词 {

    private boolean isComposeWord(Set<String> set, String word) {
        if (word.length() == 0) {
            return true;
        }
        for (int i = 0; i < word.length(); i++) {
            if (set.contains(word.substring(0, i + 1)) && isComposeWord(set, word.substring(i + 1))) {
                return true;
            }
        }
        return false;
    }

    public String longestWord(String[] words) {
        // 将单词列表按照长度降序，长度相同按照字典序
        Arrays.sort(words, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            } else {
                return o2.length() - o1.length();
            }
        });

        // 把数组做成set，提高检测的效率
        Set<String> set = new HashSet<>(Arrays.asList(words));
        // 遍历检测当前单词是不是组合单词，是的话直接返回
        for (String  word :words ) {
            set.remove(word);
            if (isComposeWord(set, word)) {
                return word;
            }
            set.add(word);
        }
        return "";
    }

    //["qlmql","qlmqlmqqlqmqqlq","mqqlqmqqlqmqqlq",
    // "mqqlq","mqqlqlmlsmqq","qmlmmmmsm","lmlsmqq","slmsqq","mslqssl","mqqlqmqqlq"]
//    public String longestWord(String[] words) {
//        Arrays.sort(words,(a,b)->{
//            if (a.charAt(0)==b.charAt(0))
//                return a.length()-b.length();
//            return a.compareTo(b);
//        });
//        for (int i = 0; i < words.length; i++) {
//            System.out.println(words[i]);
//        }
//        List<String> list = Arrays.asList(words);
//        String res="";
//        for (int i = 0; i < words.length - 1; i++) {
//            for (int j = i+1; j < words.length; j++) {
//                if (words[i].charAt(0)==words[j].charAt(0)){
//                    String left = words[j].substring(0, words[i].length());
//                    String right = words[j].substring(words[i].length());
//                    if ( left.equals(words[i]) && list.contains(right) && words[j].length()>res.length())
//                        res=words[j];
//                }
//            }
//        }
//        return res;
//    }
    @Test
    public void test(){
       String[] words={"qlmql","qlmqlmqqlqmqqlq","mqqlqmqqlqmqqlq","mqqlq","mqqlqlmlsmqq","qmlmmmmsm","lmlsmqq","slmsqq","mslqssl","mqqlqmqqlq"};
        String s = longestWord(words);
        System.out.println(s);
    }
}
